package com.lw.leetcode.arr.b;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * arr
 * b
 * 46. 全排列
 * 剑指 Offer II 083. 没有重复元素集合的全排列
 *
 * @author liw
 * @version 1.0
 * @date 2021/8/19 14:01
 */
public class Permute {
    public List<List<Integer>> permute(int[] nums) {
        int length = nums.length;
        if (length == 0) {
            return new ArrayList<>();
        }
        int a = 1;
        for (int j = 2; j <= length; j++) {
            a *= j;
        }
        List<Integer> b;
        List<List<Integer>> lists = new ArrayList<>(a);
        for (int i = 0; i < a; i++) {
            b = new ArrayList<>(length);
            lists.add(b);
        }
        aa(lists, nums, 0, a - 1);
        return lists;

    }

    public void aa(List<List<Integer>> lists, int[] nums, int st, int end) {
        int n = nums.length;
        if (n == 1) {
            lists.get(st).add(nums[0]);
            return;
        }
        int a = 1;
        for (int j = 2; j < n; j++) {
            a *= j;
        }
        int b = 0;
        for (int i = st; i <= end; i++) {
            lists.get(i).add(nums[(b++) / a]);
        }
        for (int i = 0; i < n; i++) {
            aa(lists, aa(nums, i), st + i * a, st + i * a + a - 1);
        }
    }

    public int[] aa(int[] nums, int n) {
        int l = nums.length;
        int length = l - 1;
        int[] arr = new int[length];
        for (int i = 0; i < length; i++) {
            arr[i] = i >= n ? nums[i + 1] : nums[i];
        }
        return arr;
    }
}
